#include<bits/stdc++.h>

using namespace std;

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int ret=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-(a/b)*y;
    return ret;
}

int main(int argc, char const *argv[])
{
    int a=100,a1=89,b=17,c=7;
    
    //直接取模，没啥问题
    // cout << (a*a1/b)%c <<endl;   


    //分配进去，直接出问题
    //原因在于,除法对取模不存在分配律
    // cout << (((a*a1)%c)/(b%c)) <<endl;

    cout << gcd(12,9)<<endl;
    //首先需要求逆元
    int x,y;
    cout << exgcd(12,9,x,y)<<" " <<x <<" "<<y<<endl;
    return 0;
}
